package com.yang.Offer;

import java.util.Stack;

public class Offer31 {
    public static void main(String[] args) {
        Offer31Solution offer31Solution = new Offer31Solution();
        int[] pushed = {1,2,3,4,5}, popped = {4,5,3,2,1};
        boolean b = offer31Solution.validateStackSequences(pushed, popped);
        System.out.println(b);
    }
}

class Offer31Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        // 整个过程就是用一个栈模拟压栈出栈的全过程
        // 首先按照顺序进行压栈，在这个过程中会进行是否出栈的判定
        // 如果满足就进行出栈,用while循环是满足 如果需要一直出栈的场景
        // 当所有的元素压入栈 那么循环结束 如果此时栈是空的,说明按照顺序进行了出栈 非空表示按照他的顺序无法正确出栈
        for(int num : pushed){
            stack.push(num);
            // 压栈后看看栈顶是不是本次需要出栈的对象
            while (i < pushed.length && !stack.isEmpty() && stack.peek().equals(popped[i])){
                stack.pop();
                i ++;
            }
        }
        return stack.isEmpty();
    }
}

